COMMENT ⊗   VALID 00025 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	@Make[Report]
C00008 00003	@Comment{  This, with four copies of this paper, was mailed on 29-Jan, on DHL
C00010 00004	@BEGIN[TitlePage]
C00012 00005	@Section[Introduction]
C00015 00006	@Comment[Reading Guide]
C00019 00007	@Section[New with respect to a Theory]
C00021 00008	@Comment[Semantic N]
C00042 00009	@Section[New with respect to a Symbol (and a Theory)]
C00051 00010	@BoldWord[Conjecture #1: Syntactic Method ]
C00057 00011	@BoldWord[Conjecture #2: Reduction of Interpretations ]
C00064 00012	@Comment[ @BoldWord[Analysis]
C00068 00013	@BoldWord[Conjecture #3: Partial Interpretations ]
C00073 00014	To test if @g[s] is new, therefore,
C00076 00015	A few quick notes:
C00080 00016	A tableau helps to visualize this definition.
C00083 00017	@BEGIN[Figure]
C00087 00018	@Section[Summary]
C00092 00019	@BoldWord[Uses: ]
C00098 00020	@Comment{
C00100 00021	@BoldWord["Assertional Novelty": ]
C00103 00022	@Comment{
C00104 00023	@BoldWord[Deductively Closed: ]
C00107 00024	@TEXT1{@SubHeading[Acknowledgments]
C00108 00025	@NewPage()
C00122 ENDMK
C⊗;
@Make[Report]
@Device[DOVER]
@Comment{@Style[Font=Helvetica8]}
@LIBRARYFILE<SPECIALCHARACTERS>

@Comment< @Case{Device,	FILE "@Style(Endnotes)",
		PAGEDFILE "@Style(Endnotes)"} >

@Modify[Verbatim, Break Before]
@Modify[Description, Spread 0, Spacing 1.3, LeftMargin +10, Indent -10]
@Modify[Quotation, Indent 0]
@Modify[Itemize, Referenced <@#>]
@Modify[Enumerate, Referenced <@#@;#@:.@1@,@#.@a@,@#.@i>]
@Modify[Appendix, Numbered <@A.>, Referenced <@A>]
@Modify[Equation, FaceCode T]
@Comment{ Brian said this would work... Ha!
 @Modify[NoteCounter, Referenced <@#>] }
@Style[References=STD Alphabetic]
@DEFINE[Aside=NoteStyle, LeftMargin -16, Indent 0]
@DEFINE[SubAside=Quotation,Font SmallBodyFont,FaceCode I,Spacing 1,Spread 0.5]
@DEFINE[Subsubsection,Use HdX,Font TitleFont3,FaceCode I,Above .3inch,Centered]
@DEFINE[ENUM0=ENUMERATE, NumberFrom 0, SPREAD=0, Above=0.3 line, Below=0.1 line]
@DEFINE[ENUM1=ENUMERATE, SPREAD=0.1, Spacing=1, Above=0.3 line, Below=0.1 line]
@TEXTFORM[BEGENUM1 = 
	"@BEGIN<ENUMERATE, SPREAD=0.1, Spacing=1, Above=0.3 line, Below=0.1 line>"]
@TEXTFORM[ENDENUM1 = 
	"@END<ENUMERATE>"]
@DEFINE[ITEM1=Itemize, Spread=0.1, Spacing=1, Above=0.3 line, Below=0.1 line]
@DEFINE[DESC1=Description, Spread=0, Spacing=1, Above=0.3 line, Below=0.1 line]
@DEFINE[TEXT1 = TEXT, USE NoteStyle]
@DEFINE[Tableau = Table]
@Define[NoIndent,Continue Forced,Break Around]
@Comment{ Damn  this doesn't work:
@Define[LongOnly=Comment]
@Define[BoldWord=Comment]
 Later it should be @Define[BoldWord=SubHeading, Break Before] }
@Define[BoldWord=SubHeading, Break Before,
	Above=1 line, Below=0 line]

@EQUATE[YY=R]

@Counter[EquationCounter, Numbered <(Fact @1)>, 
Referenced <(Fact @1)>, IncrementedBy tag, INIT 0]

@Counter[ConjectureCounter, Numbered <(Conjecture @1)>, 
Referenced <(Conjecture @1)>, IncrementedBy tag, INIT 0]

@DEFINE[Conjecture=Equation, Counter ConjectureCounter]

@Counter[DefnCounter, Numbered <(Definition @1)>, 
Referenced <(Definition @1)>, IncrementedBy tag, INIT 0]

@DEFINE[Defn=Equation, Counter DefnCounter]

@Counter[CaseForm,TitleEnv HD3,ContentsEnv tc3,
	  Numbered [@#@:.@1],IncrementedBy Use,Referenced <(Case @1)>,
	IncrementedBy tag, INIT 0] 

@Comment{ Now to keep from Breaking in front of chapters. }
@DEFINE(HdChap,Use HD1,PageBreak Off,Above .6inch)
@Counter(Chapter,TitleEnv HdChap,
	ContentsEnv tc1,Numbered [@1.],IncrementedBy Use,Referenced [@1],Announced) 
@Comment{How annoying!   Without this, the section numbers don't get reset!
	Note this is exactly what's in REPORT.MAK[scr,sys]. }
@Counter(Section,Within Chapter,TitleEnv HD2,ContentsEnv tc2,
	  Numbered [@#@:.@1],Referenced [@#@:.@1],IncrementedBy Use,Announced)

@Use(Bibliography =  "GENL.BIB[RDG,DBL]")
@Use(Bibliography =  "REPN.BIB[RDG,DBL]")
@Use(Bibliography = "META4.BIB[RDG,DBL]")


@Define[F1,FaceCode B,TabExport] 
@COMMENT<
@Specialfont(F1="ComputerModern10BI")
   @Define[Fancy,Font = F1,FaceCode B,TabExport] >
@Comment{  This, with four copies of this paper, was mailed on 29-Jan, on DHL
Enclosed are four copies of a paper for IJCAI-83.

	Authors:
Russell Greiner
Micheal Genesereth

	Address
HPP, Margaret Jacks Hall
Stanford University
Stanford, CA 94305-2085

	Phone:
(415) 497-1863 or (415) 497-0324

	Netmail Address:
RDG@SU-SAIL.ARPA
CSD.GENESERETH@SU-SCORE.ARPA

	Size
Short

	Subfield
"Learning and Knowledge Acquisition"

	Abstract
The central process in any learning experience is the incorporation of a
new fact into an existing theory.  Strangely, despite the abundance of
papers on learning, no one has rigorously defined what it means to be
"new".  This paper attempts to fill that gap by first stating, and then
formalizing many intuitive ideas about novelty, focussing on what it means
for a statement to be a new fact about some object, with respect to a
theory.  The report concludes with a brief discussion of how this results
might be applied, as well as the future research areas.

	Length
Abstract - about 100 words
Paper	 - 2163 words
	(excluding abstract, acknowledgment and bibligraphy)
}
@BEGIN[TitlePage]
@TitleBox{
@MajorHeading[What's New?
A Semantic Definition of Novelty]}

@i{@Value<Date>}

@Heading<Russell Greiner and Michael R. Genesereth>
@B[Heuristic Programming Project
Computer Science Department
Stanford University]

@BEGIN[TEXT, Indent 0]
@C<Abstract>:
@i{The central process in any learning experience
is the incorporation of a @r[new] fact into an existing theory.
Strangely, despite the abundance of papers on learning,
no one has rigorously defined what it means to be "new".
This paper attempts to fill that gap
by first stating, and then formalizing
many intuitive ideas about novelty,
focussing on what it means for a statement to be a new fact about
some object, with respect to a theory.
The report concludes with a brief discussion
of how this results might be applied,
as well as the future research areas.}
@END[TEXT]

@END<TitlePage>
@Section[Introduction]

@Comment[Motivation]
The central process in any learning experience
is the incorporation of a @i[new] fact into an existing theory.
Often the goal of that process is more specific,
to learn some new fact about some object.
But what does it mean to claim that a sentence is @i{new};
and, in particular, what qualifies as a novel fact about some object?
Despite the vast interest in learning and the abundance of related papers,
@Comment{(c.f. @Cite[Critic], @Cite[Learn] -- add others)}
no one has rigorously defined what it means to be "new",
either in general or with respect to a single object.

This paper attempts to fill that gap.
Our goal is to obtain
a @i[semantic] rather than @i[syntactic] understanding of novelty.
This preference stems from our belief that a semantic account 
(one based on the possible interpretations of the theory)
provides more insight into the phenomenon of novelty.
It also means we may be able
to generalize these results to other logics and languages.
@Comment{
beyond first-order predicate calculus.}

@Comment[Reading Guide]
This paper deals with two kinds of novelty.
Section @Ref[TheoryAlone] discusses the first kind of novelty,
newness of a sentence with respect to a theory.
Section @Ref[PropCase] then addresses the 
more difficult task of determining when a sentence conveys something
new about a particular object.
While the first kind of novelty is fairly easy to capture,
the second requires a consideration of the ways in which new information can
be propogated within a theory.
@Comment{  this had been foot
This is demonstrated by a series of 
simple, uncontroversial examples (and non-examples),
each demanding an increasingly more comprehensive definition.
This approach is in the style of other papers whose goal
is the formalization of some commonly used term,
c.f. @Cite[NaivePhysics], @Cite[WhatLink], @Cite[WhatConcept], @Cite[Turing].}
The concluding Section @Ref[Conclusion]
describes how our definitions can be applied
and lists many outstanding research issues.

@Section[New with respect to a Theory]
@Label[TheoryAlone]

This section will address the issue of what it means for a
sentence @g[s] to be new with respect to a theory@Foot{
In all that follows, we will assume that a theory is consistent and
deductively closed.}
@T<Th>;
this is the relation @T<N(Th,@g[s])>.
Intuitively,
we want @T<@g[s]> to be new if it (somehow) further specifies
something about the world.
Alternatively we can think of a new sentence as providing
some additional constraints --
which remove some possible worlds from consideration.

@Comment[Semantic N]
We will first consider a semantic definition of newness:
@T<@g[s]> is new if it eliminates some possible interpretation.@Foot{
We are only concerned with "true interpretations",
which map symbols onto a valid model.
We chose "interpretation" rather than "model"
to emphasize that we are dealing with a mapping rather than its range.}
That is, given any theory @F1[Th],
in the language @F1[L],
there is a set of interpretations
@T<@F1[I]@-[Th]@K[Eq]@K[LeftBrace]I@+[j]@K[RightBrace]>,
where each @T<I@+[j]> maps the symbols of 
@F1[L] onto objects or sets of tuples of objects in the "real world"@Foot{
In particular, this means that the ranges of different interpretations
can overlap;
and that the "universe" is fixed beforehand.}
in the standard way.
@Comment{That is, each constant is mapped onto an object,
and each n-ary relation onto its characteristic set --
those n-tuples that satisfy it.}

Notice that
adding additional facts to a theory can only restrict the set of
possible interpretations:
@T<Th@K[SubSet]Th'> means that
@T<@F1[I]@-[Th']@K[SubSet]@F1[I]@-[Th]>.
This leads to the proposal that
@BEGIN[DEFN]
@Tag[Defn-N-Sem]
N@-[Sem](Th,@g[s]) @K[IFF]  @~
@F1[I]@-{Th@K[PlusSign]@g[s]} @K[ProperSubSet] @F1[I]@-[Th].
@END[DEFN]

@Comment["Syntactic" N]
This same definition can be expressed syntactically,
(in terms of logical deducability rather than semantic validity,)
using
@BEGIN[DEFN]
@TAG[DefnN1]
N@-[Syn](Th,@g[s]) @K[IFF] (@g[s]@K[NotMemberOf]Th) @K[And] @~
(@K[Not]@g[s]@K[NotMemberOf]Th).
@END[DEFN]
As these are equivalent, 
(whenever the language of the theory remains fixed,
see @CITE[LogicTheory],)
we will simply use @T<N>.

@Section[New with respect to a Symbol (and a Theory)]
@Label[PropCase]

In many situations
it is not enough to realize that an assertion is new;
rather, one wants to claim that it is a new fact @i{about some object}.
With this in mind, we define the ternary relation
@T<New(Th,A,@g[s])> to mean that
the assertion @g[s] expresses a new fact about the object@Foot{
Actually, we will see later we are dealing with a syntactic symbol,
as opposed to its referent.}
@T<A> with respect to the theory @T<Th>.
The "learning step" involves adding this sentence @g[s]
(along with all of its deductive consequences)
to the theory.

What should go into a definition of @T<New(Th,s,@g[s])>?
Clearly a necessary condition is that
@T<@g[s]> be a new fact with respect to the entire theory,
i.e. @T<N(Th,@g[s])>.
But beyond that we want to capture the sense in
which @g[s] 
further specifies the object @T<A>,
or enables the derivation of additional relevant conclusions about @T<A>
@Comment{
relevant deductions which could not have been derived without this new assertion.}

This section will cover the 
@Comment{extensional,}
definitional case of @T<New>@Foot{
We will later describe this and other forms of newness.},
by presenting a series of "increasingly more nearly correct" descriptions.
For simplicity, the 
examples will be taken from propositional logic.
@Comment{
(Later we will discuss the ways this is, and is not, a limitation.)
Each proposal will begin with the intuition involved,
followed by a formal description of this conjecture,
and finally (in all but the final case) an example of the failure of this
conjecture and an analysis of this shortcoming.}

@BoldWord[Conjecture #1: Syntactic Method ]
@Label[SynMethod]
@Comment[ @BoldWord[Intuition]
Clearly most statements which relay information about some object
will contain the symbol which refers to that object.
This leads to the proposed syntactic solution:
@Comment[ @BoldWord[Conjecture]
The sentence @T<@g[s]> conveys new information about the symbol @T<A>
if the token "A" is lexically included in the string of tokens which
form @T<@g[s]>;
denoted with the assertion @T<LexInclude(A,@g[s])>.
(E.g., @T<LexInclude(A,A@K[And]B)>.)
For the reasons mentioned above,
we will further insist that @T<N(Th,@g[s])>.
Formally,
@BEGIN[Conjecture]
@Tag[G#1]
New@-[Syn](Th,A,@g[s]) @K[Iff] N(Th,@g[s]) @K[And] LexInclude(A,@g[s])
@END[Conjecture]
@Comment[ @BoldWord[Failing]
Unfortunately this syntactic condition is neither necessary nor sufficient.
To show it is not necessary, realize that we want
@T<New(@K[LeftBrace]A@K[IFF]B@K[RightBrace],A,"B")> to be true,
as asserting @T<B> in this situation
means that @T<A> must now be true;
which had not been the case before that assertion.

To show insufficiency is a little trickier.
Should
@T<New(@K[LeftBrace]A@K[Or]B@K[RightBrace],A,"A@K[Implies]B")>
be true?
We argue the answer is no:
In this context, 
asserting @T<A@K[Implies]B> is the same as asserting @T<B>,
which we know says nothing new about @T<A>.
We clearly need a more powerful method for specifying novelty.
@Label[AorB]

@BoldWord[Conjecture #2: Reduction of Interpretations ]
@Label[ReduceInter]
Using the notion of possible interpretations discussed
in Section @Ref[TheoryAlone],
we can define the "interpretation range" of a particular symbol.
Let the term @T<I@+[j][A]> designate
the "real world" referent of the symbol @T<A>,
given by the interpretation @T<I@+[j]> --
here either @u[T] or @u[F].@Foot{
The underbar notation denotes the referents of the corresponding
linguistic symbols.}
We use this to define
the interpretation range of the symbol @T<A>,
@T<@F1[I]@-[Th][A] @K[Eq] 
@K[LeftBrace]I@+[j][A] @K[Modulo] I@+[j]@K[MemberOf]@F1[I]@-[Th]@K[RightBrace]>.

As additional facts can only further restrict the range of
possible interpretations for any symbol,
we have @T<@F1{I}@-[Th'][A] @K[SubSet] @F1[I]@-[Th][A]>
whenever @T<T@K[SubSet]T'>.
This leads to our second conjecture,
@BEGIN[Conjecture]
@Tag[G#2]
New@-[FI](Th,A,@g[s])  @K[IFF]  @F1[I]@-[Th'][A] @K[ProperSubSet] @F1[I]@-[Th][A].
@END[Conjecture]

This @T<New@-[FI]> definition seems, at first, adequate.
In addition to paralleling the @T<N> situation,
it also resonates nicely with the ideas of 
Shannon Information Theory (@CITE[InfoTheory]),
in which information is tied to the
reduction of uncertainty in the distribution of
possible values of a signal.
It also handles the two cases given above 
(used to discredit @T<New@-[Syn]>).

@Comment[ @BoldWord[Failing]
Unfortunately, this @T<New@-[FI]> requirement does not include all desired cases;
there are some sentences that do convey new information
in the informal sense outlined above,
but which do not satisfy this constraint.
Start with an empty theory,
@T<Th1 @K[Gets] @K[LeftBrace]@K[RightBrace]>,
in the language @T<@F1[L]@K[Eq]@K[LeftBrace]A,B@K[RightBrace]>.
There four possible interpretations
are shown in Figure @Ref[ABValues].
@BEGIN[Figure]
@BEGIN[Verbatim, Spacing=1.1]
@tabclear
                           @↑    @↑  A   @↑B
@\@\@ux[@& @\  ]
@\I@-[0]@\| @u[F@\F]
@\I@-[1]@\| @u[F@\T]
@\I@-[2]@\| @u[T@\F]
@\I@-[3]@\| @u[T@\T]
@Caption[Interpretations of A and B]
@Tag[ABValues]
@END[Verbatim]
@END[Figure]
By inspection, @T<@F1[I]@-[Th1][A]@K[Eq]@K[LeftBrace]@un[T,F]@K[RightBrace]>.
Now form @T<Th2 @K[Gets] Th1 @K[PlusSign] A@K[IFF]B>@Comment{
This had been FOOT
The notation @T<T @K[Gets] @g[z]> means the theory @T<T> is
assigned the deductive closure of the set, @g[z];
and
@T<Th@K[PlusSign]@g[s]> refers to the deductive closure of
@T<Th@K[Union]@K[LeftBrace]@g[s]@K[RightBrace]>.}.
While this only leaves two of the four interpretations, 
@T<I@-[0]> and @T<I@-[3]>, 
@T<@F1[I]@-[Th2][A]> remains @T<@K[LeftBrace]@un[T,F]@K[RightBrace]>;
indicating that @T<A@K[IFF]B> said nothing @T<New@-[FI]> about @T<A>.

@Comment[ @BoldWord[Analysis]
Although @T<New@-[FI]> rejects this @T<A@K[IFF]B>,
we still believe it should be considered new in this situation.
Our justification is that @T<A@K[IFF]B> clearly says something about @T<A>:
if we later learn @T<@K[Not]B>, we will be able to infer that @T<@K[Not]A>,
a conclusion which would not have followed without that sentence.
That is, 
any sentence that makes @T<A>'s dependent on some other symbol,
(in the sense that @T<A@K[IFF]B> made @T<A> dependent on @T<B>)
also "feels" new.
@Comment{  PURSUE THIS:
permits certain future
statements to limit the interpretation range of @T<A>.
If forced to consider any future statement,
we would find that @i[any] sentence could be @T<New>.
Instead we only want sentences which exploit the dependency}

So there are (at least) two ways a statement can be new:
@Label[Analysis]
@BEGIN[ITEM1]
if it directly limits the interpretation range of @T<A>; or

if it establishes (or increases) a dependency of @T<A> on some other symbols
(as that may, in turn, lead to a reduction of the above type).
@END[ITEM1]
While @T<New@-[FI]> exactly covers the first case,
it fails in the second.
@BoldWord[Conjecture #3: Partial Interpretations ]
@Label[PartitionRed]
To define dependency requires an understanding of
what it means for one symbol to depend on some other symbols?
The @T<A@K[IFF]B> case above is clearly one instance of this.
In addition to such singular dependencies,
(of @T<A> on one other symbol,)
@T<A> may depend on 
a pair of symbols@Foot{
Consider the assertion @T<A@K[IFF](B@K[IFF]C)>.
Fixing any assignment to @T<B> alone,
@T<A> will still be "arbitrary" 
-- that is, it could be either @u<T> or @u<F>, depending on @T<C>.
However, if both @T<B> and @T<C> are fixed,
then @T<A> is fully determined.},
or a triple, 4-tuple, etc. of symbols.

We saw that @g[s] is a new fact about @T<A> if it 
increases @T<A> dependency on some n-tuple of symbols @T(<B@-[1],...,B@-[N]>).
That is,
given some assignment
@un{@T(<B@-[1],...,B@-[N]>)} to the symbols @T(<B@-[1],@K[Ellipsis],B@-[N]>),
asserting @g[s] restricts the set of assignments available to @T<A>.
For example, consider the assignment of @T<B> to @u<F>.
In the initial @T<Th1>, @T<A>'s value could be either @u<F> or @u<T>,
independent of this assignment of @T<B>.
However, in the enhanced @T<Th2>
@T<A> can no longer be assigned @u<T>;
its value is restricted to @u<F>.

As this
"@T(<B@-[1],@K[Ellipsis],B@-[N]>) assignment to @un{@T(<B@-[1],@K[Ellipsis],B@-[N]>)}"
reflects an assignment of only a subset of the symbols,
@T<@K[LeftBrace]B@-[i]@K[RightBrace]@K[SubSet]@F1[L]>,
we will call it a @i[partial interpretation].
Each partial interpretation corresponds to the set of (full) interpretations
which agree on the assignment of a set of symbols.
So given any @T<@g[x]@K[Subset]@F1[L]>,
the @T(<@g[x],j>) partial interpretation
@T<@K[LeftDoubleBracket]I@!@+[j]@/@-[Th]@K[RightDoubleBracket]@-{@g[x]}>
is the set of interepretations whose assignment to each symbol in
@T<@g[x]> matches the assignments of the j@+[th] full interpretation
@T<I@+[j]>.
@BEGIN[Defn]
@Tag[FancyPart]
@K[LeftDoubleBracket]I@!@+[j]@/@-[Th]@K[RightDoubleBracket]@-{@g[x]} @K[Eq] @~
@K[LeftBrace]I@K[MemberOf]@F1[I]@-[Th] @K[Modulo] @~
@K[ForAll] x@K[MemberOf]@g[x]. I[x]@K[Eq]I@+[j][x]@K[RightBrace].
@END[Defn]
The assignments of @T<A> which are consistent with
the partial interpretation
@T<@K[LeftDoubleBracket]I@!@+[j]@/@-[Th]@K[RightDoubleBracket]@-{@g[x]}> are just
@BEGIN[Defn]
@Tag[FP-A]
@K[LeftDoubleBracket]I@!@+[j]@/@-[Th]@K[RightDoubleBracket]@-{@g[x]}(A) @K[Eq] @~
@K[LeftBrace] I[A] @K[Modulo] I@K[MemberOf]@~
@K[LeftDoubleBracket]I@!@+[j]@/@-[Th]@K[RightDoubleBracket]@-{@g[x]} @K[RightBrace].
@END[Defn]

With this notation we can state that @T<A>'s dependency on
the symbols @T<@g[x]> increases if 
the set of possible values of @T<A>
consistent with some appropriate partial interpretation
@T<@K[LeftDoubleBracket]I@!@+[j]@/@-[Th]@K[RightDoubleBracket]@-{@g[x]}(A)>
decreases, but remains non-empty.@Foot{
Seeing it vanish means that there are no values of @T<A>
which are consistent with this assignment,
which means that no models can be derived from such a partial interpretation.}

To test if @g[s] is new, therefore,
consider all of the assignments available to @T<A>
for each partial interpretation,
before and after adding this new purportedly sentence @g[s].
If the number of possible referents of @T<A> decreases
for any partial interpretation, (and remains non-empty)
we will declare that @g[s] is new.
@BEGIN[Conjecture, Spacing=1.2]
@Tag[G#4]
@Tabclear
New@-[PI](Th, A, @g[s]) @K[IFF] 
   @K[Exists] @g[x] @K[SubSet] @F1[L]@K[MinusSign]@K[LeftBrace]A@K[RightBrace]. @~
@K[Exists]j. @~
(@K[LeftDoubleBracket]I@!@+[j]@/@-[Th]@K[RightDoubleBracket]@-{@g[x]}(A)@~
@K[ProperSuperSet]@~
@K[LeftDoubleBracket]I@!@+[j]@/@-[Th']@K[RightDoubleBracket]@-{@g[x]}(A)) @~
@K[And] @~
@K[LeftDoubleBracket]I@!@+[j]@/@-[Th']@K[RightDoubleBracket]@-{@g[x]}(A)@K[Neq]@~
@K[LeftBrace]@K[RightBrace]
@END[Conjecture]

A few quick notes:
@BEGIN[Enumerate]

We will say the particular partial interpretation
@T<@K[LeftDoubleBracket]I@!@+[j]@/@-[Th']@K[RightDoubleBracket]@-{@g[x]}>
which decreased in the above equation "witnessed" @g[s]'s novelty.
@Comment{wrt A}

This definition subsumes the @T<New@-[FI](Th,A,@g[s])> condition.
This follows from the fact that
@T<@K[LeftDoubleBracket]I@!@+[0]@/@-[Th]@K[RightDoubleBracket]@~
@-{@K[LeftBrace]@K[RightBrace]}(A)> is, in fact, equal to
@T<@F1[I]@-[Th][A]>.@Comment{  Had been FOOT
To the purists who try to claim that
@T<New@-[FI](Th,A,@g[s])> only means that
@T<@K[LeftDoubleBracket]I@!@+[0]@/@-[Th]@K[RightDoubleBracket]@~
@-(@K[LeftBrace]@K[RightBrace])(A) @K[ProperSuperSet]
@K[LeftDoubleBracket]I@!@+[0]@/@-[Th']@K[RightDoubleBracket]@~
@-(@K[LeftBrace]@K[RightBrace])(A)>,
and does not include the proviso that
@T<@K[LeftDoubleBracket]I@!@+[0]@/@-[Th']@K[RightDoubleBracket]@~
@-(@K[LeftBrace]@K[RightBrace])(A)@K[NEq]@K[LeftBrace]@K[RightBrace]>,
we respond that this second condition means that
@T<Th'> is consistent, which has been implicit all along.}

Were @T<A@K[MemberOf]@g[x]>,
each @T<@K[LeftDoubleBracket]I@!@+[j]@/@-[Th]@K[RightDoubleBracket]@-{@g[x]}(A)>
would be a single member.
As there are no non-proper subsets of such singleton sets,
@Comment{
no such partial interpretation could witness @g[s]'s novelty.
Hence}
it is sufficient to use
@T<@g[x]@K[SubSet]@F1[L]@K[MinusSign]@K[LeftBrace]A@K[RightBrace]>,
rather than
@T<@g[x]@K[SubSet]@F1[L]>.

Consider the set of "almost complete interpretations",
@T<@K[LeftDoubleBracket]I@!@+[j]@/@-[Th]@K[RightDoubleBracket]@~
@-{@F1[L]@K[MinusSign]A}>,
which assign all the symbols of @F1[L] except @T<A>.
Although one might believe that these partial interpretations are sufficient 
@K[Dash]
that one of these would witness any new @g[s] @K[Dash]
the counterexample below shows that is not the case.
@Tag[NeedAll]
@END[Enumerate]

A tableau helps to visualize this definition.
The left tableau in Figure @Ref[AiffB-Tableau]
corresponds to the theory @T<Th3 @K[Gets] @K[LeftBrace]A@K[IFF]B@K[RightBrace]>
in the language @T<@F1[L]@K[Eq]@K[LeftBrace]A,B,C@K[RightBrace]>;
and the one on the right to
@T<Th4 @K[Gets] Th3 @K[PlusSign] A@K[IFF]C>.
Each row is indexed by a partial interpretation,
and each column by an assignment to @T<A>.
Each tableau position is tagged with a "1" if there is 
any interpretation associated with this position,
and a "0" otherwise.
The "@T[-]"s in the far left label should be read as "don't care".  
Hence the assignment of "@T<->,@u[F]" to @T{<B,C>}
(in the fifth row) means that @T<C> must be @u[F]
while @T<B> can be any value.

A sentence is novel is there is some row, r,
in which a "1" is flipped to "0",
but which does not vanish --
i.e. r must retain a "1" in some position.
The fifth and sixth row below
(labelled "@T<->,@u[T]" and "@T<->,@u[F]") each satisfy this property,
showing that @T<New@-[PI](Th3,A,"A@K[IFF]C")>.
Notice that none of the top four rows,
which correspond to those "almost complete interpretations"
@T<@K[LeftDoubleBracket]I@!@+[j]@/@-[Th]@K[RightDoubleBracket]@~
@-{@F1[L]@K[MinusSign]A}>
have that property,
demonstrating the point of Item @Ref[NeedAll] above.
@Comment{
(These row do form an adequate spanning set, though,
as all the other rows can be derived by @T<OR>ing
together appropriate sets of these.) }

@BEGIN[Figure]
@BEGIN[Verbatim]
@tabclear
                A  
            @↑  @un[F   @↑T]  @↑                  @↑       @↑
         @\@ux[@& @\@& @\ ]
     @un[F,F]@\| 1@\0@\| @K[RightArrow] @~
@K[LeftDoubleBracket]I@!@+[0]@/@-[Th]@K[RightDoubleBracket]@~
@-{@K[LeftBrace]B,C@K[RightBrace]}  @\@K[LeftArrow] @\@K[LeftArrow]
     @un[F,T]@\| 1@\0@\| @K[RightArrow]   @K[RightArrow]   @K[RightArrow] @~
@K[LeftDoubleBracket]I@!@+[2]@/@-[Th]@K[RightDoubleBracket]@~
@-{@K[LeftBrace]B,C@K[RightBrace]}  @\@K[LeftArrow]
     @un[T,F]@\| 0@\1@\| @K[RightArrow] @~
@K[LeftDoubleBracket]I@!@+[5]@/@-[Th]@K[RightDoubleBracket]@~
@-{@K[LeftBrace]B,C@K[RightBrace]}  @\@K[LeftArrow] @\@K[LeftArrow]
     @un[T,T]@\| 0@\1@\| @K[RightArrow]   @K[RightArrow]   @K[RightArrow] @~
@K[LeftDoubleBracket]I@!@+[7]@/@-[Th]@K[RightDoubleBracket]@~
@-{@K[LeftBrace]B,C@K[RightBrace]}  @\@K[LeftArrow]
<B,C>    @\|@\@\|
     @un[-,F]@\| 1@\1@\| @K[RightArrow] @~
@K[LeftDoubleBracket]I@!@+[0]@/@-[Th]@K[RightDoubleBracket]@~
@-{@K[LeftBrace]B@K[RightBrace]}    @\@K[LeftArrow] @\@K[LeftArrow]
     @un[-,T]@\| 1@\1@\| @K[RightArrow]   @K[RightArrow]   @K[RightArrow] @~
@K[LeftDoubleBracket]I@!@+[5]@/@-[Th]@K[RightDoubleBracket]@~
@-{@K[LeftBrace]B@K[RightBrace]}  @\@K[LeftArrow]
     @un[F,-]@\| 1@\0@\| @K[RightArrow] @~
@K[LeftDoubleBracket]I@!@+[0]@/@-[Th]@K[RightDoubleBracket]@~
@-{@K[LeftBrace]C@K[RightBrace]}    @\@K[LeftArrow] @\@K[LeftArrow]
     @un[T,-]@\| 0@\1@\| @K[RightArrow]   @K[RightArrow]   @K[RightArrow] @~
@K[LeftDoubleBracket]I@!@+[2]@/@-[Th]@K[RightDoubleBracket]@~
@-{@K[LeftBrace]C@K[RightBrace]}  @\@K[LeftArrow]
         @\|@\@\|
     @un[-,-]@\| 1@\1@\| @K[RightArrow] @~
@K[LeftDoubleBracket]I@!@+[0]@/@-[Th]@K[RightDoubleBracket]@~
@-{@K[LeftBrace]@K[RightBrace]}     @\@K[LeftArrow]  @\@K[LeftArrow]
         @\@ux[|@& @\@& @\|]
@Caption(Partial Interpretations for Th3 and Th4)
@TAG[AiffB-Tableau]
@END[Verbatim]
@END[Figure]
@Section[Summary]
@Label[Conclusion]

@Label[Analysis4]
Our basic thesis is that
@g[s] is a new fact about @T<A>, with respect to the theory @T<Th>,
if, @i{under some set of circumstances,
@g[s] limits the number of interpretations available to @T<A>}.
@T<New@-[PI]> achieves this by
examining every partial interpretation,
testing each to see if @T<A> loses a possible interpretation in that situation.
This "partial interpretation" definition of context is clearly as 
general as possible.
Furthermore, by counterexample, we have shown that this 
(extreme) generality is necessary.

@Label[Obs]
While space does not permit an adequate discussion of the 
all the uses and limitations of this model of novelty,
this paper would be incomplete if it did not address
the following topics;
and point the interested reader to the longer paper @CITE[NewNess].

@BoldWord[Uses: ]
@Label[Uses]
The primary importance of this work
@Comment{, as it stands,}
is in providing a first stab at describing the different senses of newness.
In addition to the applications
a complete and adequate definition of newness would have as an
analytic tool,
(possibly leading to a definition of learning not based exclusively on performance,)
there are possible application in
Knowledge Acquisition,
(proposing ways of learning a topic more effectively,)
Representation
(e.g. suggesting that
a proposition be indexed by the symbols which find it new,)
and Discourse Analysis,
(using the realization that the purpose of speech is to communicate
new facts).

@Comment{
@BoldWord[Applicability: ]
The @T<New@-[PI]> relation described above
is applicable to any symbol in predicate calculus as well as propositional logic.
In particular, the same formalism we saw work for constant symbols
works adequately for relation symbols,
albeit with a yet even more huge tableau.

The tableau will become yet even more huge, as each column index will be a
possible characteristic set of the relation, which will be a set of n-tuples
infinite partitions, etc.
of the elements of the universe, as opposed to single elements.
Also, nothing forces the universe (which is the set of all possible referents)
to be finite -- that is, everything will follow through with infinite sets,
infinite partitions, etc.
}
@BoldWord["Assertional Novelty": ]
@Label[Assert]
The novelty we discussed above, @T<New@-[PI]>, is "definitional",
as its goal is to specify more precisely the referent of a given symbol.
Another source of novelty comes
from specifying some attribute of the object;
we label such facts "assertionally novel".
@Comment{ with respect to a theory and a symbol. }

These two categories are distinct:
Imagine the symbol @T<RDG> had been totally determined,
in the sense that the set @T<@F1[I]@-[Th][RDG]> had but a single member.
As such, there is nothing @T<New@-[PI]> we can say about @T<RDG>.

Despite this certainty,
you still might not know what his hair color is.
That is,
@T<HairColor(RDG Blond)> might be true in one interpretation,
whereas others might hold @T<HairColor(RDG Brunette)>.
Clearly @T<HairColor(RDG Brunette)> is a @T<New@-[PI]> fact about
@T<HairColor>;
however most people would also want this 
it to be a new fact about @T<RDG> as well --
i.e. @T<New@-[Assert](Th,RDG,"HairColor(RDG Brunette)")>.@Comment{
THIS HAD BEEN FOOT
There is a Strong Essentialist position which would claim that
we could not "really" have defined @T<RDG> so precisely without knowing
his hair color.
Clearly we do not take that position.}

@Comment{
@BoldWord[Intensional, not Extensional: ]
This paper only dealt with extensional phenomena,
where novelty was determined with respect to the extensions of the symbols.
Another approach is intensional -- based on descriptions.
A related research task is to find an equivalent, but
syntactical formulation of the semantical @T<New@-[PI]> relation,
in the same manner that @T<N@-[Syn]> matched @T<N@-[Sem]>.
}
@BoldWord[Deductively Closed: ]
Probably the most serious criticism of this work is its dependency on
a complete deductive system,
and the requirement that each theory be deductively closed.
New-sounding statements can also be used to focus the hearer's
attention (on some facts he already knew,)
rather that expose him to new facts.
It should be possible to extend this formalism to handle such
resource limited deduceability.
@Comment{Then we could define, and address,
topics like monotonic novelty and information obsolence.}

These issues, and many others, all seem fertile grounds for investigation.
Such explorations may very well lead to interesting, and usable, new results.
@TEXT1{@SubHeading[Acknowledgments]
We would like to especially thank
Tom Dietterich for his substantial contributions to this work.
The following people also contributed:
@Comment{Professor Douglas Lenat,}
Professor Bruce Buchanan,
@Comment{(the following logicians who helps us sort out what we should have meant:)}
Yoram Moses, Dr. Jussi Ketonen, Dr. Lew Creary,
@Comment{ and, for listening and suggesting good comments, }
Jim Davidson, Jock Mackinlay and Ben Moszkowski.
This basic research was funded by ARPA Contract #MDA903-80-C-0107.}
@NewPage()
@BEGIN[Figure]
@BEGIN[Verbatim]
@tabclear
                A
            @↑  @un[F   @↑T]  @↑
         @\@ux[@& @\@& @\ ]
@\| 1@\0@\| 
@\| 0@\0@\|
@\| 0@\0@\|
@\| 0@\1@\|
@\|@\@\|
@\| 1@\0@\|
@\| 0@\1@\|
@\| 1@\0@\|
@\| 0@\1@\|
@\|@\@\|
@\| 1@\1@\|
@\@ux[|@& @\@& @\|]

@END[Verbatim]
@END[Figure]